package algorithm;

import java.util.*;

//https://blog.csdn.net/yijianqingyu/article/details/125508493
public class 最短路径 {

    public static void main(String[] args) {

        String path = dijk("1", "3", "1-4,1-6,2-4,2-6,3-5,3-6,4-5,5-6");
        System.out.println(path);

    }

    /**
     * 最短路径
     * begin不能等于end 因为0代表不可到达的节点
     * 例
     * 输入 1,3,(1-4,1-6,2-4,2-6,3-5,3-6,4-5,5-6)
     * 输出 3 6 1
     *
     * @param begin 原点
     * @param end   目的点
     * @param path  边(格式为1-4,1-6,2-4,2-6,3-5,3-6,4-5,5-6)
     * @return
     */
    public static String dijk(String begin, String end, String path) {
        //存放所有的节点,用hashset 可以防止重复
        HashSet<String> allNode = new HashSet<>();
        //存放所有的边,每个map代表一条边,有三个参数,start,end,weight,开始节点,结束节点,长度
        List<Map<String, String>> edgeList = new ArrayList<>();
        //记录当前要到达节点,按照示例,当我在1号位的时候,pathList 应包含4节点,6节点两条数据
        List<Map<String, String>> pathList = new ArrayList<>();
        //到达指定节点,需要的距离key-节点 value-最小距离
        Map<String, Integer> nodePath = new HashMap<>();
        //因为要返回路径,所以需要该map记录,最后根据这个map倒推路径 最终获取数据的map,key-结束节点 value(map key pre上一节点,end结束节点,len 长度)
        Map<String, Map<String, String>> minpathMap = new HashMap<>();

        //解析边的数据,完成allNode和edgeList的装载
        String[] paths = path.split(",");
        for (int i = 0, j = paths.length; i < j; i++) {
            String[] nodes = paths[i].split("-");
            allNode.add(nodes[0]);
            allNode.add(nodes[1]);
            Map<String, String> map1 = new HashMap<>();
            map1.put("start", nodes[0]);
            map1.put("end", nodes[1]);
            map1.put("len", "1");
            edgeList.add(map1);
            Map<String, String> map2 = new HashMap<>();
            map2.put("start", nodes[1]);
            map2.put("end", nodes[0]);
            map2.put("len", "1");
            edgeList.add(map2);
        }
        //递归法,我先获取到本节点的距离,再计算可达到的下一节点,循环计算,直到全部计算以后
        //初始化时要先到达开始节点,设置距离为0
        Map<String, String> startNode = new HashMap<>();
        startNode.put("len", "0");
        startNode.put("pre", begin);
        startNode.put("end", begin);
        nodePath.put(begin, 0);
        pathList.add(startNode);
        //初始化赋值到每个节点的长度为null
        for (String name : allNode) {
            minpathMap.put(name, null);
        }
        //无可达节点则退出
        while (pathList.size() > 0) {
            //先取出第一个要到达的节点
            Map<String, String> pathMap = pathList.remove(0);
            String endNodeName = pathMap.get("end");
            //获取到达该节点需要的距离
            Integer len = Integer.parseInt(pathMap.get("len"));
            //记录到达该节点的线路
            minpathMap.put(endNodeName, pathMap);
            //记录到达该节点的长度
            nodePath.put(endNodeName, len);
            //遍历边,获取接下来要达到的节点
            for (Map<String, String> edgeMap : edgeList) {
                //遍历所有的边,如果有从当前节点走向下一节点的,将下一节点加入pathList,下次循环计算
                if (edgeMap.get("start").equals(endNodeName)) {
                    String newEnd = edgeMap.get("end");
                    Integer newLen = Integer.parseInt(edgeMap.get("len"));
                    Integer lenA = nodePath.get(newEnd);
                    //如果要到达的节点去过了,并且路径更短,则不沿着该边过去(有更短的路径了)
                    if (lenA == null || lenA > len + newLen) {
                        nodePath.put(newEnd, len + newLen);
                        Map<String, String> newMap = new HashMap<>();
                        newMap.put("len", len + newLen + "");
                        newMap.put("pre", endNodeName);
                        newMap.put("end", newEnd);
                        pathList.add(newMap);
                    }
                }
            }
        }
        //不可达输出0
        if (nodePath.get(end) == null) {
            return "0";
        }
        //此时我们已经计算好到达每条路径的距离了,我们需要输出路径pathStr
        //先输出结束节点
        //结束节点的前一节点
        String pre = minpathMap.get(end).get("pre");
        //结束节点
        String pathStr = end;
        //如果结束节点的前一节点不是开始节点,则取前一节点的前一节点,直到开始节点
        while (!begin.equals(pre)) {
            pathStr = pathStr + " " + minpathMap.get(pre).get("end");
            pre = minpathMap.get(pre).get("pre");
        }
        pathStr = pathStr + " " + begin;
        return pathStr;
    }

}
